package com.dyz.leetcode;

import java.util.Arrays;

public class FindMedianSortedArrays4 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1,3,5,7,9};
        int[] nums2 = new int[]{2,4,6,8,10,12};
        double media = new FindMedianSortedArrays4().findMedianSortedArrays1(nums1, nums2);
        System.out.println(media);
    }
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if((nums1==null||nums1.length==0)&&(nums2==null || nums2.length==0)){return -1;}
        if(nums1==null||nums1.length==0){return media(nums2);}
        if(nums2==null||nums2.length==0){return media(nums1);}
        int n1 = nums1.length;
        int n2 = nums2.length;
        int [] nums3 = new int[n1+n2];
        int index = 0;
        for(Integer val:nums1){
            nums3[index++] = val;
        }
        for(Integer val:nums2){
            nums3[index++] = val;
        }
        Arrays.sort(nums3);
        return media(nums3);

    }

    private double media(int[] nums){
        int n = nums.length;
        if(n%2==0){
            return ((nums[n/2-1] + nums[n/2])/2.0);
        }else {
            return nums[n/2];
        }
    }

    // 二分法
    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        //默认nums1是更短的
        //如果nums1更长，交换num1和nums2。
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;
        // median1：前一部分的最大值
        // median2：后一部分的最小值
        int median1 = 0, median2 = 0;

        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;//数组1的分割点
            int j = (m + n + 1) / 2 - i;//数组2的分割点

            //对数组越界的情况巧妙地处理
            int nums1a = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int nums1b = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int nums2a = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int nums2b = (j == n ? Integer.MAX_VALUE : nums2[j]);

            if (nums1a <= nums2b) {
                median1 = Math.max(nums1a, nums2a);//各自左半边的最大值
                median2 = Math.min(nums1b, nums2b);//各自右半边的最小值
                left = i + 1;
            }
            else {
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }

    //比较好理解的解题思路
    public double findMedianSortedArrays5(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //小的数组在前
        if(m>n){
            return findMedianSortedArrays5(nums2, nums1);
        }

        int start = 0;
        int end = m;

        double result =0.0;

        while(start<=end){
            int mid = (start+end)/2; //num1 左边贡献多少个
            int other = (m+n+1)/2-mid;//num2 左边贡献多少个，+1的目的是当m+n是奇数时，保证左边个数大于右边个数

            int num1LeftMax = mid==0?Integer.MIN_VALUE:nums1[mid-1];
            int num1RightMin = mid==m?Integer.MAX_VALUE:nums1[mid];
            int num2LeftMax = other==0?Integer.MIN_VALUE:nums2[other-1];
            int num2RightMin = other==n?Integer.MAX_VALUE:nums2[other];

            if(num1LeftMax <= num2RightMin && num1RightMin >= num2LeftMax ){
                //m+n是偶数个
                if((m+n)%2 == 0){
                    int leftVal = Math.max(num1LeftMax, num2LeftMax); //两个数组的左边取最大值
                    int rightVal = Math.min(num1RightMin, num2RightMin);//两个数组的左边取最小值
                    result = (leftVal+rightVal)/2.0;
                    //m+n是奇数个
                }else{
                    result =  Math.max(num1LeftMax, num2LeftMax); //因为左边永远大于右边个数，只要取左边最大就可以了
                }
                break;
            }else if(num1RightMin < num2LeftMax){
                start = mid + 1;
            }else{
                end = mid -1;
            }
        }
        return result;
    }


    public double findMedianSortedArrays2(int[] nums1, int[] nums2){
        //令nums1是更短的那个数组
        if(nums1.length>nums2.length){
            return findMedianSortedArrays(nums2, nums1);
        }
        int start=0;
        int end= nums1.length;

        boolean wholeIsEven=(nums1.length+nums2.length)%2==0;

        //(start, end)
        while (true){
            int partitionX = start + (end-start)/2;
            int partitionY = (nums1.length+nums2.length)/2-partitionX;
            int xLeftMax = (partitionX-1<0)? Integer.MIN_VALUE:nums1[partitionX-1];
            int xRightMIn = (partitionX>=nums1.length)? Integer.MAX_VALUE:nums1[partitionX];
            int yLeftMax = (partitionY-1<0)? Integer.MIN_VALUE:nums2[partitionY-1];
            int yRightMin = (partitionY>=nums2.length)?Integer.MAX_VALUE:nums2[partitionY];

            //return 情况， 左边小于右边，对角比较
            if(xLeftMax<=yRightMin && yLeftMax<=xRightMIn){
                if(wholeIsEven){
                    return (double)(Integer.max(xLeftMax, yLeftMax) +Integer.min(xRightMIn, yRightMin))/2;
                }else {
                    return (double)(Integer.min(xRightMIn, nums2[partitionY]));
                }
            }
            //XleftMax比yRightMin大 左移动
            if(xLeftMax>yRightMin){
                end = partitionX;
            }
            //yLeftMax比xrightMin小右移动
            if(yLeftMax>xRightMIn){
                start = partitionX+1;
            }
        }

    }
}
